package com.eslog.entity;

import java.util.HashMap;
import java.util.Map;

public class Test {

    /**
     *作业一：数据结构与算法基础
     *  判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只出现过一次。例如，arr = {1, 2, 3}，输出 YES。
     *  又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
     */
    public static String work1(int[] arr){

        if(arr == null){
            return "NO";
        }

        Map<Integer,Boolean> map = new HashMap<>();

        for(int i=0;i<arr.length;i++){
            Boolean val = map.get(arr[i]);
            if(val!=null && val){
                return "NO";
            }
            map.put(arr[i],true);
        }
        return "YES";
    }

    /**
     *作业二：数据结构与算法高级
     *  很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；
     *  有的金矿储量是200kg黄金，需要3个工人来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。
     *  要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     */
    public static int work2(int[] kg,int[] personNum,int max){
        if(kg==null || kg.length==0) return 0;
        if(personNum==null || personNum.length==0) return 0;
        if(kg.length!=personNum.length || max<=0) return 0;
        int[][]dp=new int[kg.length+1][max+1];
        for(int i=1;i<=kg.length;i++){
            for(int j=1;j<=max;j++){
                if(j<personNum[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max((dp[i-1][j]),kg[i-1]+dp[i-1][j- personNum[i-1]]);
                }
            }
        }

        int maxValue = dp[kg.length][max];

        int j = max;
        for(int i=kg.length; i>0; i--){
            //若果dp[i][j]>dp[i-1][j],这说明i是放入的
            if(dp[i][j]>dp[i-1][j]){
                System.out.println("挖取第"+i+"座金矿: "+kg[i-1]);
                j=j-personNum[i-1];
            }
            if(j==0) break;
        }
        return maxValue;
    }

    public static void main(String[] args) {
        //题目一
        int[] arr = {1, -2222, 12,-2222};
        System.out.println(work1(arr));

        int[] arr1 = {1, 3, 123,-2222};
        System.out.println(work1(arr1));

        //题目二
        int[] kg={900,700,500,200,100};
        int[] personNum={8,7,5,3,2};
        int max=10;
        System.out.println("最多黄金："+work2(kg,personNum,max));
    }

}
